﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ShortestPath
{
    class BinaryHeap : PriorityQueue//实现最小堆，实现优先队列接口
    {
        /**
    * Construct the binary heap.
    */
        private Position _pos;
        public BinaryHeap()
        {
            currentSize = 0;
            array = new IComparable[DEFAULT_CAPACITY + 1];
            //position = new Position();
        }

        public Position position
        {
            get
            {
                return _pos;
            }
            set
            {
                _pos = value;
            }
        }

        /**
         * Construct the binary heap from an array.
         * @param items the inital items in the binary heap.
         */
        public BinaryHeap(IComparable[] items)
        {
            currentSize = items.Length;
            array = new IComparable[items.Length + 1];

            for (int i = 0; i < items.Length; i++)
                array[i + 1] = items[i];
            buildHeap();
        }
        private void doubleArray()
        {
            IComparable[] tmp;
            tmp = new IComparable[array.Length];
            for (int i = 0; i < array.Length; i++)
            {
                tmp[i] = array[i];
            }
            array = new IComparable[2 * tmp.Length];
            for (int i = 0; i < tmp.Length; i++)
            {
                array[i] = tmp[i];
            }
        }

        /**
         * Insert into the priority queue.
         * Duplicates are allowed.
         * @param x the item to insert.
         * @return null, signifying that decreaseKey cannot be used.
         */
        public Position insert(IComparable x)
        {
            if (currentSize + 1 == array.Length)
                doubleArray();

            // Percolate up
            int hole = ++currentSize;
            array[0] = x;

            for (; x.CompareTo(array[hole / 2]) < 0; hole /= 2)
                array[hole] = array[hole / 2];
            array[hole] = x;

            return null;
        }

        /**
         * @throws UnsupportedOperationException because no Positions are returned
         * by the insert method for BinaryHeap.
         */
        public void decreaseKey(Position p, IComparable newVal)
        {
            throw new Exception("Cannot use decreaseKey for binary heap");
        }

        /**
         * Find the smallest item in the priority queue.
         * @return the smallest item.
         * @throws UnderflowException if empty.
         */
        public IComparable findMin()
        {
            if (isEmpty())
                throw new Exception("Empty binary heap");
            return array[1];
        }

        /**
         * Remove the smallest item from the priority queue.
         * @return the smallest item.
         * @throws UnderflowException if empty.
         */
        public IComparable deleteMin()
        {
            IComparable minItem = findMin();
            array[1] = array[currentSize--];
            percolateDown(1);

            return minItem;
        }

        /**
         * Establish heap order property from an arbitrary
         * arrangement of items. Runs in linear time.
         */
        private void buildHeap()
        {
            for (int i = currentSize / 2; i > 0; i--)
                percolateDown(i);
        }

        /**
         * Test if the priority queue is logically empty.
         * @return true if empty, false otherwise.
         */
        public bool isEmpty()
        {
            return currentSize == 0;
        }

        /**
         * Returns size.
         * @return current size.
         */
        public int size()
        {
            return currentSize;
        }

        /**
         * Make the priority queue logically empty.
         */
        public void makeEmpty()
        {
            currentSize = 0;
        }

        private static readonly int DEFAULT_CAPACITY = 100;

        private int currentSize;      // Number of elements in heap
        private IComparable[] array; // The heap array

        /**
         * Internal method to percolate down in the heap.
         * @param hole the index at which the percolate begins.
         */
        private void percolateDown(int hole)
        {
            int child;
            IComparable tmp = array[hole];

            for (; hole * 2 <= currentSize; hole = child)
            {
                child = hole * 2;
                if (child != currentSize &&
                        array[child + 1].CompareTo(array[child]) < 0)
                    child++;
                if (array[child].CompareTo(tmp) < 0)
                    array[hole] = array[child];
                else
                    break;
            }
            array[hole] = tmp;
        }
    }
}
